/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-21 19:52:10
 * @LastEditors: lily
 * @LastEditTime: 2021-04-22 10:48:44
 */
/*
 * @lc app=leetcode.cn id=41 lang=javascript
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */

//  思路：哈希表
//  <= 0的数为无效数据，将有效数据存入obj
//  res从1开始比较，找到最小的

//  使用nums作为存储可以将空间复杂度变为O(1)
//  https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

var firstMissingPositive = function (nums) {
    // 自做  复杂度：O(n) O(n)
    // let obj = {}, res = 1
    // for (let n of nums) {
    //     if (n > 0) {
    //         obj[n] = 1
    //     }
    // }
    // while (obj[res]) {
    //     res++
    // }
    // return res

    // 原地哈希  复杂度：O(n) O(1)
    const n = nums.length
    // 将负数变为n+1
    for (let i = 0; i < n; i++) {
        if (nums[i] <= 0) {
            nums[i] = n + 1
        }
    }
    // 将<n+1的元素对应位置元素变为相反数
    for (let i = 0; i < n; i++) {
        // 这里取abs是防止后面的数已经变为负数
        let num = Math.abs(nums[i])
        if (num < n + 1) {
            nums[num - 1] = -Math.abs(nums[num - 1])
        }
    }
    // 返回第一个>0的元素的下标
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1
        }
    }
    return n + 1
};
// @lc code=end

console.log(firstMissingPositive([3, 4, -1, 1]));